import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-17
 * Time: 20:28
 */
public class TestDemo1 {


    public static List<String> subs(String str){
        //ans代表我要将没有做决定的各种排列加到ans里面去
        List<String> ans = new ArrayList<>();
        String path = "";//代表之前做了哪些决定
        int index = 0;//从0开始
        //将从0位置开始将0位置以后的所有子序列加入到ans中
        char[] ch = str.toCharArray();
        process(ch,index,ans,path);
        return ans;
    }

    //path代表之前的决定---->代表之前都要谁没要谁
    //ans就代表答案---将path已经确没有做决定的全部子序列加入到ans中
    //所以这就是在path为""也就是在0位置做决定时,将0位置以后的全部子序列加入到ans中
    public static void process(char[] str,int index,List<String> ans,String path){
        if(index==str.length){//如果下标超过了字符串长度,就终止,
            ans.add(path);//就将之前做的决定加入到答案中
            return;
        }
        //对于遍历到index+1位置时候,我没要index位置的字符
        process(str,index+1,ans,path);
        //对于遍历到index+1位置时候,我要了index位置的字符
        process(str,index+1,ans,path+String.valueOf(str[index]));
    }


    public static HashSet<String> subs1(String str){
        //ans代表我要将没有做决定的各种排列加到ans里面去
        HashSet<String> ans = new HashSet<>();
        String path = "";//代表之前做了哪些决定
        int index = 0;//从0开始
        //将从0位置开始将0位置以后的所有子序列加入到ans中
        char[] ch = str.toCharArray();

        process1(ch,index,ans,path);
        return ans;
    }

    //path代表之前的决定---->代表之前都要谁没要谁
    //ans就代表答案---将path已经确没有做决定的全部子序列加入到ans中
    //所以这就是在path为""也就是在0位置做决定时,将0位置以后的全部子序列加入到ans中
    public static void process1(char[] str,int index,HashSet<String> ans,String path){
        if(index==str.length){//如果下标超过了字符串长度,就终止,
            ans.add(path);//就将之前做的决定加入到答案中
            return;
        }
        //对于遍历到index+1位置时候,我没要index位置的字符
        process1(str,index+1,ans,path);
        //对于遍历到index+1位置时候,我要了index位置的字符
        process1(str,index+1,ans,path+String.valueOf(str[index]));
    }



    //打印全排列
    public static List<String> permutation(String s){
        if(s==null||s.length()==0){
            return null;
        }
        List<Character> rest = new ArrayList<>();
        char[] ch = s.toCharArray();
        for(char c : ch){
            rest.add(c);
        }
        String path = "";
        List<String> ans = new ArrayList<>();
        process2(s,rest,path,ans);
        return ans;
    }

    public static void process2(String s,List<Character> rest,String path,
                                List<String> ans){
        if(rest.isEmpty()){
            ans.add(path);//如果没有字符了就把之前做的决定加进去
        }else {
            int sz = rest.size();
            for(int i =0;i< sz;++i){
                //拿到当前字符--并从rest中删除
                char cur = rest.get(i);
                rest.remove(i);
                process2(s,rest,path+cur,ans);
                //回溯过程,对下一个字符在进行全排列的时候要还原现场
                rest.add(i,cur);
            }
        }
    }


    public static List<String> permutation2(String s){
        if(s==null||s.length()==0){
            return null;
        }
        List<String> ans = new ArrayList<>();
        char[] ch = s.toCharArray();
        int index = 0;
        process3(ch,index,ans);
        return ans;
    }

    public static void process3(char[] str,int index,List<String> ans){
        if(index==str.length){
            ans.add(String.valueOf(str));
        }else {
            boolean[] visited = new boolean[256];
            for(int i=index;i< str.length;++i){
                if(!visited[i]) {
                    visited[i] = true;
                    swap(str, index, i);
                    process3(str, index + 1, ans);
                    swap(str, index, i);
                }
            }
        }
    }

    public static void swap(char[] ch,int i,int j){
        char tmp = ch[i];
        ch[i] = ch[j];
        ch[j] = tmp;
    }

//    public static void reverse(Stack<Integer> stack){
//        if(stack.isEmpty()){
//            return;
//        }
//        int i = process4(stack);
//        reverse(stack);
//        stack.push(i);
//    }
//
//    public static int process4(Stack<Integer> stack){
//        int res = stack.pop();
//        if(stack.isEmpty()){
//            return res;
//        }
//        int last = process4(stack);
//        stack.push(last);
//        return last;
//    }



    public static void reverse(Stack<Integer> stack){
        if(stack.isEmpty()){
            return;
        }
        int i = process(stack);
        reverse(stack);
        stack.push(i);
    }

    public static int process(Stack<Integer> stack){
        int res = stack.pop();
        if(stack.isEmpty()){
            return res;
        }else {
            int last = process(stack);
            stack.push(res);
            return last;
        }
    }


    public static void main(String[] args) {
//        List<String> list = subs("acccccccc");
//        for(String x : list){
//            System.out.println(x);
//        }
//        System.out.println("============================");
//        HashSet<String> list1 = subs1("acccccccc");
//        for(String x : list1){
//            System.out.println(x);
//        }
//        List<String> ret =  permutation2("abc");
//        for(String x : ret){
//            System.out.println(x);
//        }
//
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        System.out.println(stack);
        reverse(stack);
        System.out.println(stack);
    }

}
